package sort.test3_27;

public class GuiBingSort4{
    //归并　 就是后序遍历
//    先　划分
//    在合并
    public int[] guibingSort(int [] nums){
        if (nums.length==0){
            return  null;
        }
        int[] temp = new int[nums.length];
        sort(nums,0, nums.length-1,temp );
        return  nums;
    }

    public void  sort(int[] nums,int lo,int hi,int[] temp){
        if (lo>=hi){
            return;
        }
        int  mid=(lo+hi)/2;
        sort(nums,lo,mid,temp);
        sort(nums,mid+1,hi,temp);
        merge(nums,lo,mid,hi,temp);
    }

    //todo:忘记的逻辑　用temp数组去接收排完顺序后的数组　　然后 zai dui yuan shi shu zu jin xing tiao huan
    // todo:先排序一小部分　然后再不断扩大排序顺序　　最终将整个数组排序完毕
      public  void merge(int[] nums,int lo,int mid,int hi,int[] temp){
        int i=0;
        int p=lo;
        int q=mid+1;
        while (p<=mid&&q<=hi){
            //todo:不要在这个地方进行p++ q++
            if (nums[p]<=nums[q]){
                //todo:在这个地方　进行p++  q++
                temp[i++]=nums[p++];
            }
            else {
                temp[i++]=nums[q++];
            }
        }
        while (p<=mid){
            temp[i++]=nums[p++];
        }
        while (q<=hi){
            temp[i++]=nums[q++];
        }
        for (int j = 0; j <i ; j++) {
            nums[lo+j]=temp[j];
        }

    }

    public static void main(String[] args) {
        GuiBingSort4 guiBingSort3 = new GuiBingSort4();
        int[] nums=new int[] {5, 8, 2, 4, 1,7};
        guiBingSort3.guibingSort(nums);
        for (int a: nums
        ) {
            System.out.println(a);

        }
    }






}
